package bucketSort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class BucketSort {

    /**
     * 桶排序实现
     * @param list 需要排序的数组
     * @return 排序完成的额数组
     */
    public static List<Double> bucketSort(List<Double> list){
        //先计算最大最小元素
        double max = list.get(0);
        double min = list.get(1);
        for (Double target : list) {
            if (target >= max) max = target;
            if (target <= min) min = target;
        }
        double different = max - min;
        //初始化桶
        int bucketNumber = list.size();
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNumber);
        for (int i = 0; i < list.size(); i++) {
            bucketList.add(new LinkedList<>());
        }
        //遍历原数组 并将元素入桶
        for (Double target : list) {
            //计算放入那个桶
            int num = (int)((target - min) * (bucketNumber - 1) / different);
            bucketList.get(num).add(target);
        }
        //对桶内的元素排序
        bucketList.forEach(item -> {
            Collections.sort(item);
        });
        //输出全部的元素
        ArrayList<Double> resourceList = new ArrayList<>();
        //当前需要初始化
        for (int i = 0; i < bucketNumber; i++) {
            resourceList.add(0.0);
        }
        AtomicInteger index = new AtomicInteger();
        bucketList.forEach(item ->{
            item.forEach(element -> {
                resourceList.set(index.get(),element);
                index.incrementAndGet();
            });
        });
        return resourceList;
    }
}
